package com.cb2.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/isomorphic-strings/">同构字符串(Isomorphic Strings)</a>
 * <p>给定两个字符串 s 和 t ，判断它们是否是同构的。</p>
 * <p>如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。</p>
 * <p>每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1:
 *      输入：s = "egg", t = "add"
 *      输出：true
 *
 * 示例 2：
 *      输入：s = "foo", t = "bar"
 *      输出：false
 *
 * 示例 3：
 *      输入：s = "paper", t = "title"
 *      输出：true
 *     </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length <= 5 * 10^4</li>
 *     <li>t.length == s.length</li>
 *     <li>s 和 t 由任意有效的 ASCII 字符组成</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/21 16:52
 */
public class LC0205IsomorphicStrings_S {
    static class Solution {
        public boolean isIsomorphic(String s, String t) {
            Map<Character, Character> s2tMap = new HashMap<>();
            Map<Character, Character> t2stMap = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char sC = s.charAt(i);
                char tC = t.charAt(i);
                // 如果s->t的映射中，已经存在sChar的映射关系
                if (s2tMap.containsKey(sC)) {
                    // 如果映射关系不是tChar，返回false。
                    // 因为再与tChar建立关系就会出现s中一个字符对应t中两个字符的情况。
                    if (s2tMap.get(sC) != tC) {
                        return false;
                    }
                }
                // 如果t->s的映射中，已经存在tChar的映射关系
                else if (t2stMap.containsKey(tC)) {
                    // 如果映射关系不是sChar，返回false。
                    // 因为再与sChar建立关系就会出现t中一个字符对应s中两个字符的情况。
                    if (t2stMap.get(tC) != sC) {
                        return false;
                    }
                } else {
                    // 建立映射关系
                    s2tMap.put(sC, tC);
                    t2stMap.put(tC, sC);
                }
            }
            return true;
        }
    }
}
